COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "setup.csr[bib,csr]" source file
C00004 00003	%3STAN-CS-80-828:
C00018 00004	%3STAN-CS-80-829:
C00020 00005	%3STAN-CS-80-830:
C00022 00006	%3STAN-CS-80-831:
C00025 00007	%3STAN-CS-81-839:
C00027 00008	%3STAN-CS-80-831:
C00031 ENDMK
C⊗;
.require "setup.csr[bib,csr]" source file;
.once center
%3Stanford University Computer Science Reports%1
List Number 11↔March 1981

Listed here are abstracts of the most recent reports published by the
Department of Computer Science at Stanford University.

%3Request Reports:%1 Complete the enclosed order
form, and return the entire order form page (including mailing label) 
as soon as possible.  In many cases we can print only a limited number of copies,
and requests will be filled on a first come, first served basis as the reports
become available.  If the code
(FREE) is printed on your mailing label, you will not be charged for hardcopy.
This exemption from payment is limited primarily to libraries.  (The costs
shown include all applicable sales taxes.  %2Please send
no money now, wait until you get an invoice.%1)

%3Alternatively:%1 Copies of most Stanford CS Reports may be obtained by writing
(about 2 months after the ''Most Recent CS Reports'' listing) to 
National
Technical Information Service, 5285 Port Royal Road, Springfield, Virginia 22161.
Stanford Ph.D. theses are available from University Microfilms, 300 North
Zeeb Road, Ann Arbor, Michigan 48106.

-↔-

%3STAN-CS-80-828:
%2Breaking Paragraphs Into Lines%1
by Donald E. Knuth and Michael F. Plass (66 pages, November 1980)

This paper discusses a new approach to the problem of dividing the text
of a paragraph into lines of approximately equal length. Instead of simply making
decisions one line at a time, the method considers the paragraph as a whole, so
that the final appearance of a given line might be influenced by the text on
succeeding lines. A system based on three simple primitive concepts called
'boxes', 'glue', and 'penalties' provides the ability to deal satisfactorily
with a wide variety of typesetting problems in a unified framework, using a
single algorithm that determines optimum breakpoints. This algorithm avoids
backtracking by a judicious use of the techniques of dynamic programming.
Extensive computational experience confirms that the approach is both
efficient and effective in producing high-quality output. The paper concludes
with a brief history of line-breaking methods, and an appendix presents a
simplified algorithm that requires comparatively few resources.

-↔-

%3STAN-CS-80-829:
%2The Dinner Table Problem%1
by Bengt Aspvall and Frank Liang (13 pages, December 1980)

This report contains two papers inspired by the "dinner table problem":
If %2n%1 people are seated randomly around a circular table for two meals, what is
the probability that no two people sit together at both meals?  We show that
this probability approaches  %2e∩[-2]%1 as  %2n → %5α∞%1, and also give a closed form.  We
then observe that in many similar problems on permutations with restricted
position, the number of permutations satisfying a given number of properties is
approximately Poisson distributed.  We generalize our asymptotic argument to
prove such a limit theorem, and mention applications to the problems of
derangements, menages, and the asymptotic number of Latin rectangles.

-↔-

%3STAN-CS-80-830:
%2Two Linear-Time Algorithms for Five-Coloring a Planar Graph%1
by David Matula, Yossi Shiloach and Robert Tarjan (23 pages, December 1980)

A "sequential processing" algorithm using bicolor interchange that five-
colors an  %2n%1 vertex planar graph in O(%2n%1↑2) time was given by Matula,
Marble, and Isaacson [MMI 72].  Lipton and Miller used a "bach processing"
algorithm with bicolor interchange for the same problem and achieved an improved
O(%2n%1 log %2n%1)time bound [LM 78].  In this paper we use graph contraction
arguments instead of bicolor interchange and improve both the sequential 
processing and batch processing methods to obtain five-coloring algorithms
that operate in O(%2n%1) time.

-↔-
%3STAN-CS-80-831:
%2An O(nm log n) Algorithm for Maximum Network Flow%1
by Daniel D. K. Sleator (Thesis, 81 pages, December 1980)

This thesis presents a new algorithm for the maximum network flow problem.  The
problem is this: Given a directed network of %2m%1 edges and %2n%1 vertices with
two distinguished vertices, a source and a sink, and with a nonnegative capacity
associated with each edge, find a way of labeling the edges with nonnegative real
numbers representing flow in such a way that:

(1) The flow into each vertex equals the flow out (except at the source and sink).
(2) The flow at each edge does not exceed the capacity at that edge.
(3) The flow out of the source is a maximum over-all flow satisfying (1) and (2).

Our algorithm finds a maximum flow in %2(nm%1log%2n%1) time, which is a factor of
log %2n%1 faster than the previous fastest algorithm.

Our algorithm finds a maximum flow in O(%2nm%1log%2n%1) time, which is a factor
of log %2n%1 faster than the previous fastest algorithm.  The central innovation
of our algorithm is a sophisticated data structure that is used to represent a
certain subset of edges that form a forest.  The edges of this forest are further
partitioned into two classes: broken and solid.  Long paths of solid edges are 
grouped together and stored in a balanced tree data structure called a biased 2-3 
tree.  Each leaf of the biased 2-3 tree corresponds to an edge in the path.
%3STAN-CS-81-839:
%2Short Waits%1
by Arthur L. Samuel (37 pages, February 1981)

This is an introductory manual describing the SU-AI timesharing system
that is available primarily for sponsored research in the Computer Science 
Department.  The present manual is written for the beginner and the user interested
primarily in the message-handling capability as well as for the experienced
computer user and programmer who either is unfamiliar with the SU-AI computer or
who uses it infrequently.  References are made to the available hard-copy manuals
and to the extensive on-line document files where more complete information can be 
obtained.

The principal advantages of this system are:

1) The availability of a large repertoire of useful system features; 2) The large
memory; 3) The large file-storage system; 4) The ease with which one can access
other computers via the ARPA net; 5) The file transfer facilities via the EFTP
program and the ETHERNET; 6) The XGP and the DOVER printers and the large
collections of fonts available for them; and 7) The fast and convenient E editor
with its macro facilities.

-↔-
%3STAN-CS-80-831:
%2An O(nm log n) Algorithm for Maximum Network Flow%1
by Daniel D. K. Sleator (81 pages, December 1980)

This thesis presents a new algorithm for the maximum network flow problem.  The
problem is this:  Given a directed network of %2m%1 edges and %2n%1 vertices with
two distinguished vertices, a source and a sink, and with a nonnegative capacity
associated with each edge, find a way of labeling the edges with nonnegative real
numbers representing flow in such a way that:

(1) The flow into each vertex equals the flow out (except at the source and sink).
(2) The flow at each edge does not exceed the capacity at that edge.
(3) The flow out of the source is a maximum over-all flow satisfying (1) and (2).

Our algorithm finds a maximum flow in  O(%2nm%1log%2n%1) time, which is a factor
of log %2n%1 faster than the previous fastest algorithm.  The central innovation
of our algorithm is a sophisticated data structure that is used to represent
a certain subset of edges that form a forest.  The edges of this forest are
further partitioned into two classes: broken and solid.  Long paths of solid edges
are grouped together and stored in a balanced tree data structure called a biased
2-3 tree.  Each leaf of the biased 2-3 tree corresponds to an edge in the path.

The most significant property of this data structure is that it allows a variety
of operations to be performed in  O(log %2n%1) time.  Some of these are: The 
traversal from any leaf of the tree to the root while accumulating information about
the edges along the path (e.g. finding the minimum capacity edge); the updating of
information stored at each edge (e.g. changing the current value of the flow); 
certain types of tree rearrangements (e.g. removing a subtree and attaching it 
somewhere else).

It appears that this data structure can be used to get fast algorithms for other
problems such as the transshipment problem, the deepest common ancestor
problem where a cut operation is allowed, and the two-color minimum spanning
tree problem.

-↔-